import com.sun.source.tree.Tree;

import java.util.*;

public class BinatyTree {
    public static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }

    }

    public TreeNode root;

    public void createTree() {
        TreeNode a = new TreeNode('A');
        TreeNode b = new TreeNode('B');
        TreeNode c = new TreeNode('C');
        TreeNode d = new TreeNode('D');
        TreeNode e = new TreeNode('E');
        TreeNode f = new TreeNode('F');

        root = a;
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.right = f;
    }

    //前序遍历
    public void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    //中序遍历
    public void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    //后序遍历
    public void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

    //  // 获取树中节点的个数
    public int size(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return size(root.left) + size(root.right) + 1;
    }

    //    // 获取叶子节点的个数
    int getLeafNodeCount(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
    }

    //    // 子问题思路-求叶子结点个数
//// 获取第K层节点的个数
    public int getKLevelNodeCount(TreeNode root, int k) {
        if (root == null) {
            return 0;
        }
        if (k == 0) {
            return 1;
        }

        return getKLevelNodeCount(root.left, k - 1) +
                getKLevelNodeCount(root.right, k - 1);
    }

    //    // 获取二叉树的高度
    int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftTreeHigh = getHeight(root.left);
        int rightTreeHigh = getHeight(root.right);
        return Math.max(leftTreeHigh, rightTreeHigh) + 1;
    }

    //    // 检测值为value的元素是否存在
    TreeNode find(TreeNode root, char val) {
        if (root == null) {
            return null;
        }
        if (root.val == val) {
            return root;
        }
        TreeNode leftTree = find(root.left, val);
        if (leftTree.val == val) {
            return leftTree;
        }
        TreeNode rightTree = find(root.right, val);
        if (rightTree.val == val) {
            return rightTree;
        }
        return null;

    }
//    //层序遍历
//    void levelOrder(Node root);
//    // 判断一棵树是不是完全二叉树
//    boolean isCompleteTree(Node root);

    /**
     * 检验两棵树是否相同
     *
     * @param p
     * @param q
     * @return
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if ((p == null && q != null) || (p != null && q == null)) {
            return false;
        }
        if (p == null && q == null) {
            return true;
        }

        if (p.val != q.val) {
            return false;
        }

        if (isSameTree(p.left, q.left) && isSameTree(p.right, q.right)) {
            return true;
        }
        return false;
    }

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) {
            return false;
        }
        if (isSameTree(root, subRoot)) {
            return true;
        }
        if (isSubtree(root.left, subRoot)) {
            return true;
        }
        if (isSubtree(root.right, subRoot)) {
            return true;
        }
        return false;
    }

    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }

        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        int leftHight = getHeight(root.left);
        int rightHight = getHeight(root.right);
        if (Math.abs(leftHight - rightHight) > 1) {
            return false;
        }
        return isBalanced(root.left) && isBalanced(root.right);
    }


    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isSymmetric(root.left, root.right);
    }

    public boolean isSymmetric(TreeNode leftTree, TreeNode rightTree) {
        if (leftTree != null && rightTree == null ||
                leftTree == null && rightTree != null) {
            return false;
        }
        if (leftTree == null && rightTree == null) {
            return true;
        }
        if (leftTree.val != rightTree.val) {
            return false;
        }

        return isSymmetric(leftTree.left, rightTree.right) &&
                isSymmetric(leftTree.right, rightTree.left);
    }

    //层序遍历
//    void levelOrder(TreeNode root){
//        Queue<TreeNode> queue = new LinkedList<>();
//        queue.offer(root);
//        while(!queue.isEmpty()){
//            TreeNode cur = queue.poll();
//            System.out.print(cur.val + " ");
//            if(cur.left != null){
//                queue.offer(cur.left);
//            }
//            if(cur.right != null){
//                queue.offer(cur.right);
//            }
//        }
//    }

    public List<List<Character>> levelOrder(TreeNode root) {
        List<List<Character>> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) {
            return null;
        }
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Character> tmpList = new ArrayList<>();
            int size = queue.size();
            while (size > 0) {
                TreeNode cur = queue.poll();
                tmpList.add(cur.val);
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
                size--;
            }
            list.add(tmpList);
        }
        return list;
    }


    public boolean isCompleteTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur != null) {
                queue.offer(root.left);
                queue.offer(root.right);
            } else {
                break;
            }

        }
        while (!queue.isEmpty()) {
            TreeNode cur = queue.peek();
            if (cur == null) {
                queue.poll();
            } else {
                return false;
            }
        }
        return true;

    }

//    public TreeNode lowestCommonAncestor(TreeNode root,
//                                         TreeNode p, TreeNode q) {
//        if (root == null) return null;
//        if (root == q || root == p) return root;
//        TreeNode leftTree = lowestCommonAncestor(root.left, p, q);
//        TreeNode rightTree = lowestCommonAncestor(root.right, p, q);
//        if (leftTree != null && rightTree != null) {
//            return root;
//        } else if (leftTree != null) {
//            return leftTree;
//        } else {
//            return rightTree;
//        }
//    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Stack<TreeNode> stackP = new Stack<>();
        Stack<TreeNode> stackQ = new Stack<>();
        findVal(stackP, root, p);
        findVal(stackQ, root, q);
        int sizeP = stackP.size();
        int sizeQ = stackQ.size();
        if(sizeP > sizeQ){
            int size = sizeP - sizeQ;
            while(size > 0){
                stackP.pop();
                size--;
            }
        }else{
            int size = sizeQ - sizeP;
            while(size > 0){
                stackQ.pop();
                size--;
            }
        }

        while(!stackP.empty() && !stackQ.empty()){
            TreeNode valP = stackP.peek();
            TreeNode valQ = stackQ.peek();
            if(valQ == valP){
                return valQ;
            }else{
                stackP.pop();
                stackQ.pop();
            }
        }

        return null;
    }

    public static boolean findVal(Stack<TreeNode> stack,
                                  TreeNode root, TreeNode key) {

        if (root == null) {
            return false;
        }
        stack.push(root);

        if (root == key) {
            return true;
        }
        Boolean flg = findVal(stack,root.left, key);
        if(flg){
            return true;
        }
        flg = findVal(stack,root.right,key);
        if(flg){
            return true;
        }
        stack.pop();
        return false;


    }

//    public int postIndex = 0;
//
//    public TreeNode buildTree(int[] postorder, int[] inorder) {
//        postIndex = postorder.length-1;
//        return buildTree(postorder, inorder, 0, inorder.length-1);
//    }
//
//    public TreeNode buildTree(int[] postorder, int[] inorder, int ibegin,
//                              int iend) {
//        if(ibegin > iend){
//            return null;
//        }
//
//        TreeNode root = new TreeNode(postorder[postIndex]);
//        int rooti = findVal(inorder,ibegin, iend, postorder[postIndex]);
//        postIndex--;
//
//        root.right = buildTree(postorder, inorder, rooti+1, iend);
//        root.left = buildTree(postorder, inorder, ibegin, rooti-1);
//
//        return root;
//
//    }
//
//    private int findVal(int[] inorder, int ibegin, int iend, int key){
//        for(int i = ibegin; i <= iend; i++){
//            if(inorder[i] == key){
//                return i;
//            }
//        }
//        return -1;
//    }

    public String tree2str(TreeNode root) {
        StringBuilder str = new StringBuilder();
        tree2strChild(root, str);
        return str.toString();
    }

    public void tree2strChild(TreeNode root, StringBuilder str){
        if(root == null) return;
        str.append(root.val);
        //左子树
        if(root.left != null){
            str.append('(');
            tree2strChild(root.left, str);
            str.append(')');
        }else{
            if(root.right == null){
                return;
            }else{
                str.append("()");
            }
        }
        //右子树
        if(root.right != null){
            str.append('(');
            tree2strChild(root.right, str);
            str.append(')');
        }else{
            return;
        }


    }

    public List<Character> preorderTraversal(TreeNode root) {
        List<Character> ret = new ArrayList<>();
        if(root == null) return ret;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.empty()) {
            while (cur != null) {
                stack.push(cur);
                ret.add(cur.val);
                cur = cur.left;
            }
            cur = stack.pop();
            cur = cur.right;
        }

        return ret;
    }

    public List<Character> inorderTraversal(TreeNode root) {
        List<Character> ret = new ArrayList<>();
        if(root == null) return ret;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            ret.add(cur.val);
            cur = cur.right;
        }
        return ret;
    }

    public List<Character> postorderTraversal(TreeNode root) {
        List<Character> ret = new ArrayList<>();
        if(root == null) return ret;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null){
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.peek();
        cur = cur.right;

    }

}



